﻿//#define FAILURE
//#define RESULTS
//#define GOTO

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics.Contracts;
using System.Linq;

namespace Elderos.TextSearchers
{
	public class AhoCorasickSearcherHash : TextSearcherBase
	{
		private Automaton _automaton = new Automaton();

		#region Overrides of TextSearcherBase

		private int _loadedStringsCount;

		public override int LoadedStringsCount
		{
			get { return _loadedStringsCount; }
		}

		protected override IEnumerable<Position> InnerSearch(string text)
		{
			var results = new List<Position>();
			Node currentNode = _automaton.Root;
			for (int i = 0; i < text.Length; i++)
			{
				Node nextNode;
				do
				{
					nextNode = _automaton.Goto(currentNode, text[i]);
					if (nextNode == null)
						currentNode = _automaton.Fail(currentNode);
				} while (nextNode == null);

				currentNode = nextNode;

				IEnumerable<int> nodeResults =
					_automaton.GetNodeResults(currentNode);

				if (nodeResults != null)
				{
					results.AddRange(
						nodeResults.Select(
							length => new Position(i - length + 1, length)));
				}
			}

			return results;
		}

		protected override void ProcessString(string str)
		{
			_loadedStringsCount++;

			Node currentNode = _automaton.Root;
			for (int i = 0; i < str.Length; i++)
			{
				char currentChar = str[i];

#if GOTO
				Dictionary<char, Node> childrenDict;
				if (!_automaton.GotoDict.TryGetValue(currentNode, out childrenDict))
				{
					childrenDict = new Dictionary<char, Node>();
					_automaton.GotoDict.Add(currentNode, childrenDict) ;
				}
#else
				if (currentNode.Children == null)
					currentNode.Children = new Dictionary<char, Node>();

				Dictionary<char, Node> childrenDict = currentNode.Children;
#endif


				if (childrenDict.ContainsKey(currentChar))
				{
					currentNode = childrenDict[currentChar];
					if (i == str.Length - 1)
					{
#if RESULTS
						if (_automaton.ResultsDict.ContainsKey(currentNode))
							_automaton.ResultsDict[currentNode].Add(str.Length);
						else
							_automaton.ResultsDict.Add(currentNode,
													   new List<int>
														   {str.Length});
#else
						if (currentNode.Results != null)
							currentNode.Results.Add(str.Length);
						else
							currentNode.Results = new List<int> { str.Length };
#endif
					}
					continue;
				}

				var nextNode = new Node();
				childrenDict.Add(currentChar, nextNode);
				if (i == str.Length - 1)
				{
#if RESULTS
					if (_automaton.ResultsDict.ContainsKey(nextNode))
						_automaton.ResultsDict[nextNode].Add(str.Length);
					else
						_automaton.ResultsDict.Add(nextNode,
												   new List<int> {str.Length});
#else
					if (nextNode.Results != null)
						nextNode.Results.Add(str.Length);
					else
						nextNode.Results = new List<int> { str.Length };
#endif
				}

				currentNode = nextNode;
			}
		}

		protected override void OnStringsLoaded()
		{
			base.OnStringsLoaded();
			_automaton.ProcessNodeFailures();
		}

		#endregion

		private class Automaton
		{
			public Automaton()
			{
#if FAILURE
				_failureDict.Add(_root, _root);
#else 

#endif
			}

			private Node _root = new Node();

			public Node Root
			{
				get { return _root; }
			}

#if FAILURE
private Dictionary<Node, Node> _failureDict =
	new Dictionary<Node, Node>();

public Dictionary<Node, Node> FailureDict
{
	get { return _failureDict; }
}
#endif

#if RESULTS
private Dictionary<Node, List<int>> _resultsDict =
	new Dictionary<Node, List<int>>();

public Dictionary<Node, List<int>> ResultsDict
{
	get { return _resultsDict; }
}
#endif

#if GOTO
private Dictionary<Node, Dictionary<char, Node>> _gotoDict =
	new Dictionary<Node, Dictionary<char, Node>>();

public Dictionary<Node, Dictionary<char, Node>> GotoDict
{
	get { return _gotoDict; }
}
#endif

			public void ProcessNodeFailures()
			{
				var queue = new Queue<Node>();

				Dictionary<char, Node> rootChildren;
#if GOTO
				if (!GotoDict.TryGetValue(_root, out rootChildren))
					rootChildren = new Dictionary<char, Node>();
#else
				rootChildren = _root.Children;
#endif

				foreach (var node in rootChildren.Values)
					queue.Enqueue(node);

				while (queue.Count > 0)
				{
					Node node = queue.Dequeue();

					Dictionary<char, Node> children;

#if GOTO
					if (!GotoDict.TryGetValue(node, out children))
						children = new Dictionary<char, Node>();
#else
					children = node.Children;
					if (children == null)
						continue;
#endif

					foreach (var kv in children)
					{
						Node child = kv.Value; //child = u
						char ch = kv.Key;

						queue.Enqueue(child);
						Node failure = Fail(child); //failure = v
						while (Goto(failure, ch) == null)
							failure = Fail(failure);

						Node failureDestination = Goto(failure, ch);

						if (failureDestination != _root)
#if FAILURE
							_failureDict.Add(child, failureDestination);
#else
							child.FailureNode = failureDestination;
#endif

#if RESULTS
						if (_resultsDict.ContainsKey(failure))
						{
							if (!_resultsDict.ContainsKey(child))
								_resultsDict.Add(child, new List<int>());
							_resultsDict[child].AddRange(_resultsDict[failure]);
						}
#else
						if (failure.Results != null)
						{
							if (child.Results == null)
								child.Results = new List<int>();
							child.Results.AddRange(failure.Results);
						}
#endif
					}
				}
			}

			public Node Goto(Node fromNode, char ch)
			{
				Node outNode;
#if GOTO
				Dictionary<char, Node> children;
				if (GotoDict.TryGetValue(fromNode, out children) 
					&& children.TryGetValue(ch, out outNode)) 
					return outNode;
#else
				if (fromNode.Children != null 
					&& fromNode.Children.TryGetValue(ch, out outNode)) 
					return outNode;
#endif
				if (fromNode == _root)
					return _root;
				return null;
			}

			public Node Fail(Node fromNode)
			{
#if FAILURE
				Node outNode;
				if (FailureDict.TryGetValue(fromNode, out outNode))
					return outNode;
				return _root;
#else
				return fromNode.FailureNode ?? _root;
#endif
			}

			public IEnumerable<int> GetNodeResults(Node node)
			{
#if RESULTS
				List<int> lengths;
				if (ResultsDict.TryGetValue(node, out lengths))
					return lengths;
				return null;
#else
				return node.Results;
#endif
			}
		}

		private class Node
		{
#if !GOTO
			public Dictionary<char, Node> Children { get; set; }
#endif

#if !FAILURE
			public Node FailureNode { get; set; }
#endif

#if !RESULTS
			private List<int> _results;
			public List<int> Results
			{
				get { return _results; }
				set { _results = value; }
			}
#endif

			public override string ToString()
			{
				return "Node: " + GetHashCode();
			}
		}
	}
}
